package com.mlh.linkedlist;

//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表开始相交的起始节点。如果两个链表没有交点，返回 null 。
//这边相交之后两个链表就不会分开，在一个链表上面
//输入两个链表，找出它们的第一个公共节点
public class GetIntersectionNode {
    //第一种想法：创建一个set把一个链表的所有节点丢进去
    //然后第二条链表从头开始丢  发现重复的就是第一个公共节点
    //此时空间和时间复杂度都是o(n)

    //第二种想法：先遍历两条链表算出长度然后计算出两条链表的差值
    //让长链表先走差值步，然后两条链表同时走，每走一步都判断节点是否相同
    //此时时间复杂度是o(n) 空间复杂度是o(1)
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pA=headA;
        ListNode pB=headB;

        //走到一个节点为空
        while (pA!=null&&pB!=null){
            pA= pA.next;
            pB= pB.next;
        }
        //如果A为空
        if(pA==null){
            pA=pB;
            pB=headB;
            while(pA!=null){
                pA= pA.next;
                pB=pB.next;
            }
            pA=headA;
            while (pA!=null){
                if(pA==pB){
                    return pA;
                }
                pA= pA.next;
                pB= pB.next;
            }
            return null;
        }else {//如果B为空
            pB=pA;
            pA=headA;
            while(pB!=null){
                pB= pB.next;
                pA=pA.next;
            }
            pB=headB;
            while (pA!=null){
                if(pA==pB){
                    return pA;
                }
                pA= pA.next;
                pB= pB.next;
            }
            return null;
        }
    }

    //第三种想法(leetcode学习)
    //使用双指针  其本质上和方法二的思想是一模一样的 但是他的写法简单了很多  高度code
    //且这个写法在两条链长度相同时，能够更快返回公共节点
    //时间复杂度是o(n) 空间复杂度是o(1)
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }


}
